#include "dynamic_memory.h"
#include "kprint.h"

static header* free_list; //lists the free blocks in the heap

/* initializes the heap data structure to make it usable */
void initialize_heap(){
  //initially, everything is empty
  free_list = (header*) HEAP_LOWEST_ADDRESS;
  free_list->next = NULL;
  free_list->size = HEAP_SIZE-1;
  free_list->status = STATUS_FREE;
}

/* allocates size bytes (+ sizeof(header)) on behalf of pid and returns a pointer to the allocated area. Returns NULL if out of memory */
void* malloc(int32_t size, int32_t pid){
  header* current;
  int32_t needed = size + sizeof(header);
  for(current = free_list; current != NULL; current = current->next){
    //is the current block free and big enough? 
    if(current->status == STATUS_FREE && current->size >= needed){
      //yes, it is
      header* new_header;
      int32_t remaining = current->size - needed;
      if(remaining > sizeof(header)){
	/* the remaining block can still be used to allocate something
	   /!\ data alignment ! new_header's address must be a multiple of 4. The following code ensures that but creates small holes of a few bytes. They are recycled during a free operation. 
	*/
	new_header = (header*) ((char*)current + needed); //starting address of the next block
	//adjust address for data alignment
	uint32_t diff = (uint32_t)new_header % 4;
	if(diff)
	  new_header = (header*)((char*)new_header + 4 - diff);
	new_header->next = current->next;
	new_header->size = current->size - (needed+4-diff);
	new_header->status = STATUS_FREE;
	current->next = new_header;
      }
      current->size = needed;
      current->status = STATUS_USED;
      current->allocated_by = pid;
      //returns a pointer to the allocated area (just after the header)      
      return ((char*)current + sizeof(header));
    }
  }
  // nothing usable found, allocation failed
  return NULL;
}

/* free the area pointer by pointer. If pointer does not point to an area allocated by malloc, FAILURE is returned. Returns SUCCESS otherwise.  */
int32_t free(void* pointer, int32_t pid){
  if(pointer == NULL)
    return FAILURE;
  //restores the header (hidden from the programmer)
  header* to_free = (header*)((char*)pointer-sizeof(header));
  header* current, *prev = NULL;
  for(current = free_list; current != NULL; prev = current, current = current->next){
    if(current == to_free){
      //found the correct block, we mark it as free and try to merge it with its neighbors
      if(current->status != STATUS_USED || (current->allocated_by != pid && pid != SYSTEM_ID)){
	return FAILURE; //the block to free was not allocated and/or do not free your buddy's stuff. The system can bypass the last case.
      }
      free_and_merge(prev, &to_free, to_free->next);
      return SUCCESS;
    }		 
  }
  return FAILURE;
}

/* tests if pointer can be merged with prev and/or next and do it. */
void free_and_merge(header* prev, header** pointer, header* next){
  header* current;
  uint32_t size;
  int32_t p_size = (*pointer)->size;
  header* p_next = (*pointer)->next;
  //deallocate pointer 
  (*pointer)->status = STATUS_FREE;

  //now, we try to merge pointer with prev
  if(prev != NULL){
    current = prev;
    //if there is an unusable piece of memory between prev and pointer, it is size bytes-long
    size = (char*)(*pointer) - ((char*)prev+prev->size);
    if(prev->status == STATUS_FREE){
      //prev itself is free, we merge it with pointer (without forgetting the eventual chunk between them)
      set_header(current, current->size+p_size+size, p_next,STATUS_FREE);
    }else {
      if(size > 0){
	//just free the chunk by modifying pointer
	//moving pointer back
	*pointer = (header*)((char*)current + current->size);
	//but we need to respect the alignment 
	uint32_t diff = (uint32_t)(*pointer) % 4;
	if(diff)
	  *pointer = (header*)((char*)(*pointer) + 4 - diff);
	current->next = (*pointer);
	set_header(*pointer, size+p_size-(4-diff), p_next, STATUS_FREE);
      }
      current = current->next;
    }
  }else
    current = *pointer;
  
  //here, current points either on the merged cell or on pointer (because prev wasn't free)
  //now, check if we have to merge current with next
  if(next != NULL){
    //like before, check for an unused chunk of memory
    size = (char*)next - ((char*)current+current->size);
    if(next->status == STATUS_FREE){
      //merge everything in one cell
      set_header(current, current->size+next->size+size, next->next, STATUS_FREE);
    }else if(size > 0){
      //here, we just have to extend current's size
      current->size += size;
    }
  }
}

/* sets the information of a header */
void set_header(header* pointer, uint32_t size, header* next, uint32_t status){
  pointer->size = size;
  pointer->next = next;
  pointer->status = status;
}

/* frees all the blocks owned by pid. Called to avoid memory leaks when a process terminates */
void free_all_pid(int32_t pid){
  header* current, *prev = NULL;
  for(current = free_list; current != NULL; prev = current, current= current->next){
    if(current->allocated_by == pid){
      free_and_merge(prev, &current, current->next);
    }
  }
}
